# coding = UTF-8
# @Time : 2021/12/07 19:08
# @Author : PP_YY
# @File : Montgomery.py
# @descrision : 蒙哥马利算法实现
import numpy

def findmodreverse(num1,num2): # 求模逆
    if numpy.gcd(num1,num2) != 1:
        return None
    u1,u2,u3 = 1,0,num1
    v1,v2,v3 = 0,1,num2
    while v3 != 0:
        q = u3//v3
        v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
    return u1%num2


def square_mutliply(a,n,N): # 平方乘
    m = bin(n)[2:][::-1]
    k = len(m)
    d = 1
    for i in range(k-1,-1,-1):
        d = montgomery(d, d, N)
        if m[i] == 1:
            d = montgomery(d, a, N)
    return d
    
    
def find_R(N): # 预处理中的R
    R = 1
    k = 0
    while R <= N:
        R *= 2
        k += 1
    while numpy.gcd(R,N) != 1:
        R *= 2
        k += 1
    return R,k

def find_X(a,b,N,R): # 预处理中的X
    a1 = (a*R) % N
    b1 = (b*R) % N
    X = a1*b1
    return X

def find_m(N,R,X): # m值
    N1 = findmodreverse(N, R)
    m = (X * (R%N1) ) % R
    return m

def montgomery_reduction(X,R,N,k): # 蒙哥马利约减算法
    m = find_m(N, R, X)
    y = (X + m*N) >> k
    if y > N:
        y -= N
    return y

def montgomery(a,b,N): # 蒙哥马利模乘算法
    R,k = find_R(N)
    X = find_X(a, b, N, R)
    X1 = montgomery_reduction(X, R, N, k)
    y = montgomery_reduction(X1, R, N, k)
    return y



def main():
    a = int(input("input a")) # 底数
    n = int(input("input n")) # 指数
    N = int(input("input N")) # 模数
    mod = square_mutliply(a, n, N)
    print(mod)


if __name__ == "__main__":
    main()